|
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for . The operator is called a ''jump operator'' because it increases the Turing degree of the problem . That is, the problem is not Turing reducible to . Post's theorem establishes a relationship between the Turing jump operator and the arithmetical hierarchy of sets of natural numbers. Informally, given a problem, the Turing jump returns the set of Turing machines which halt when given access to an oracle that solves that problem. == Definition == Given a set and a Gödel numbering of the functions, the Turing jump of is defined as : The th Turing jump is defined inductively by : : The jump of is the effective join of the sequence of sets for : : where denotes the th prime. The notation or is often used for the Turing jump of the empty set. It is read ''zero-jump'' or sometimes ''zero-prime''. Similarly, is the th jump of the empty set. For finite , these sets are closely related to the arithmetic hierarchy. The jump can be iterated into transfinite ordinals: the sets for , where is the Church-Kleene ordinal, are closely related to the hyperarithmetic hierarchy. Beyond , the process can be continued through the countable ordinals of the constructible universe, using set-theoretic methods (Hodes 1980). The concept has also been generalized to extend to uncountable regular cardinals (Lubarsky 1987). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing jump」の詳細全文を読む スポンサード リンク
|